Section: Application Domains

Transportation and logistics

• Scheduling problems: The flow-shop scheduling problem is one of the most well-known problems from scheduling. However, most of the works in the literature use a single-objective formulation. In general, the minimized objective is the total completion time (makespan). Many other criteria may be used to schedule tasks on different machines: maximum tardiness, total tardiness, mean job flowtime, number of delayed jobs, maximum job flowtime, etc. In the DOLPHIN project, a bi-criteria model, which consists in minimizing the makespan and the total tardiness, is studied. Multiple combinations of two objective functions have also been investigated. At last, a three-objective flow-shop problem, minimizing in addition the maximum tardiness, is also studied. It allows us to develop and test multi-objective (and not only bi-objective) exact methods.

• Routing problems: The vehicle routing problem (VRP) is a well-known problem and it has been studied since the end of the fifties. It has a lot of practical applications in many industrial areas (ex. transportation, logistics, etc). Existing studies of the VRP are almost all concerned with the minimization of the total distance only. The model studied in the DOLPHIN project introduces a second objective, whose purpose is to balance the length of the tours. This new criterion is expressed as the minimization of the difference between the length of the longest tour and the length of the shortest tour. As far as we know, this model is one of the pioneer works in the literature. One of our current goals, related to an Inria ADT project, is to a propose VRP library called VRP-solve that is able to cope with a multiple objective and a large number of constraints. This code will be used in future industrial collaborations, and already includes algorithms to use GIS.

• Packing problems: In logistic and transportation fields, packing problems may be a major issue in the delivery process. They arise when one wants to minimize the size of a warehouse or a cargo, the number of boxes, or the number of vehicles used to deliver a batch of items. These problems have been the subjects of many papers, but only few of them study multi-objective cases, and to our knowledge, never from an exact point of view. Such a case occurs for example when some pairs of items cannot be packed in the same bin. The DOLPHIN project is currently studying the problem in its one-dimensional version. We plan to generalize our approach to two and three dimensional problems, and to more other conflict constraints, with the notion of distance between items.